/* ==================================================================
* Copyright (c) 2024/11/15 SCNU LiuJunJie z-ken
* All rights reserved.
* fileName:	reToNFA.hpp
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the
* distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the xxx Group. and
* its contributors.
* 4. Neither the name of the Group nor the names of its contributors may
* be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY Author,GROUP AND CONTRIBUTORS
* ===================================================================
* Author: LiuJunJie z-ken.
*/

#include "Base.hpp"
#include "libs.hpp"
#include "func_read.hpp"
#include "MyObject.hpp"
#if !defined(RE_TO_DFA)
#define RE_TO_DFA
#define M_TAB 1


class reToNFA
{
public:
    int nfa2_start = -1; // 未初始化前，起点和终点为-1
    int nfa2_end = -1;

public:
    unordered_set<string> punc;        // 符号集合
    unordered_set<string> expressions; // 重复检测
    // 坐标定义
    unordered_map<string, int> expressionToColumn;    // 已经加入的正则表达式
    unordered_map<string, string> name_re_expression; // 复合的正则表达式

    int size1 = 0;            // 基本正则变量的size
    int rowNum = 0;           // NFA的行数
    int baseLength = 0;       // 基本正则变量的size
    int NFA2_node_number = 1; // NFA2的节点编号或者是个数，其数值是节点编号的最大值加1（相当于行号），所以遍历时需要 从i到NFA2_node_number-1

    vector<Base> resualt;             // 记录所有的加入的基本re
    vector<vector<vector<int>>> NFA;  // 定义：行是节点编号，列是re的序号，存放的是下一个状态的节点编号,实际上NFA1记录的是接收到的正则的种类，不参与正则的表达式运算
    vector<vector<vector<int>>> NFA2; // 定义：行是节点编号，列是re的序号，存放的是下一个状态的节点编号

    string origin;           // 原始表达式
    string updatedString;    // 添加了与符号的表达式
    string fileName;         // 文件router
    int needReplace = false; // 是否需要替换先前定义的变量
    int startLine = 0;       // 开始读文件的位置
    int breakLine = 0;       // 文件读取结束的位置
    int totalLine = 0;       // 文件的总行数
    string tokenName = "";   // 下划线开始的名称

    reToNFA()
    {
        cout << "开辟空间中--START" << endl;
        // 内存开辟
        this->NFA = vector<vector<vector<int>>>(NFA_SIZE);
        for (int i = 0; i < NFA_SIZE; ++i)
        {
            NFA[i] = std::vector<std::vector<int>>(NFA_SIZE_RE_2);
        }
        this->NFA2 = vector<vector<vector<int>>>(NFA_SIZE);
        for (int i = 0; i < NFA_SIZE; ++i)
        {
            NFA2[i] = std::vector<std::vector<int>>(NFA_SIZE_RE_2);
        }
        cout << "开辟空间--END" << endl;

        // 加入基础符号
        // {"|", "*", "+", "?", "(", ")","[","]"} // 要求的符号
        resualt.push_back(Base("1", "#"));
        expressionToColumn["#"] = 0;
        vector<string> punc_s({"|", "*", "+", "?", "(", ")"}); // 运算符号
        punc = unordered_set<string>(punc_s.begin(), punc_s.end());
    }

    void setNeedReplace(int newState)
    {
        needReplace = newState;
    }

    std::string ReplaceAll(std::string subject, const std::string &search, const std::string &replace)
    {
        size_t pos = 0;
        while ((pos = subject.find(search, pos)) != std::string::npos)
        {
            subject.replace(pos, search.length(), replace);
            pos += replace.length(); // 处理下一个可能的匹配
        }
        return subject;
    }

    void preRead()
    {
        int n = 100;
        string re1;

        vector<string> rows = UtilFunc::readFile(fileName);
        cout << "有 " << rows.size() << " 条数据，" << "开始位置为line:" << startLine << endl;
        this->totalLine = rows.size();
        for (int i = this->startLine; i < rows.size(); i++)
        {
            string name = "1";
            string re_Name, re2;
            // re1 = (rows[i]); // 会保留空格
            re1 = LibUtil::trim(rows[i]);

            if (rows[i].empty())
            {
                continue; // 跳过空行
            }

            if (re1[0] == '_')
            {
                // 记录退出行数
                tokenName = re1.substr(0, re1.find("="));
                this->breakLine = i;
                break;
            }
            re_Name = re1.substr(0, re1.find("="));
            if (re1.find("=") + 1 <= re1.size())
            {
                re2 = re1.substr(re1.find("=") + 1);
            }
            Base newBase(name, re_Name);
            if (newBase.regular_Expression.size() != 0)
            {
                // addRe(newBase); // 不需要添加了
                name_re_expression[re_Name] = re2;
            }
        }
        origin = re1.substr(re1.find("=") + 1);

        if (this->needReplace == true)
        {
            // 需要将先前定义的letter或digit进行替换
            for (auto pi : name_re_expression)
            {
                origin = this->ReplaceAll(this->origin, pi.first, pi.second);
            }
        }

        cout << "preRead.解压前: " << origin << endl;
        origin = preParse(origin);
    }

    /**
     * 在字符串中，寻找一个未转义字符的位置
     */
    int findNoTransferChar(string s, char c)
    {
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == c && i == 0)
            {

                return i;
            }
            else if (s[i] == c && i >= 1 && s[i - 1] != '\\')
            {
                return i;
            }
        }
        return -1;
    }

    string preParse(string s)
    {
        while (findNoTransferChar(s, '[') != -1)
        {
            int st1 = findNoTransferChar(s, '[');
            int end1 = findNoTransferChar(s, ']');
            if (st1 != -1)
            {
                string sub1 = s.substr(st1, end1 - st1 + 1);
                string newSub1 = BaseUtils::parseComplexRe(sub1);
                s.replace(s.begin() + st1, s.begin() + end1 + 1, newSub1);
            }
        }
        cout << "此次解压后的:" << s << endl;
        return s;
    }

    void make(string fileName1)
    {
        fileName = fileName1;
        preRead();              // 读入
        readBasicRe(origin, 0); // 获取小型正则表达式
    }

    bool inPunc(string s)
    {
        return punc.find(s) != punc.end();
    }

    bool inExpressionToColumn(string s)
    {
        bool res = (expressionToColumn.find(s) != expressionToColumn.end());
        return res;
    }

    void readBasicRe(string s, int startIndex)
    {
        // 初始化
        for (int i = startIndex; i < s.size(); i++)
        {
            if (inPunc(s.substr(i, 1)) && ((i == 0) || (i > 0 && s[i - 1] != '\\')))
            {
                continue;
            }
            Base newBase = readBase(s, i);

            // 更新i
            if (newBase.regular_Expression.size() != 0)
            {
                i += newBase.regular_Expression.size() - 1;
                if (inExpressionToColumn(newBase.regular_Expression) == 0) // 如果没有重复添加
                {
                    addRe(newBase);
                }
            }
        }
        baseLength = size1;
    }

    Base readBase(string s, int startIndex)
    {
        string name = "0";
        string re = "";
        // 按规律寻找（寻找可能是定义的变量）
        for (int i = startIndex; i < s.length(); i++)
        {
            if (inPunc(s.substr(i, 1)) && ((i == 0) || (i > 0 && s[i - 1] != '\\'))) // 如果不是转义字符，离开
            {
                break;
            }
            re.push_back(s[i]);
        }

        if (inExpressionToColumn(re) == 0) // 没有重复,并且不是已经定义的变量
        {
            if (s[startIndex] == '\\') // 转义字符
            {
                re = s.substr(startIndex, 2);
                return Base(name, re);
            }
            else if (s[startIndex] == '[')
            {
            }
            re = s.substr(startIndex, 1);
            return Base(name, re);
        }

        return Base(name, re);
    }

    void show_res()
    {
        for (auto p : resualt)
        {
            cout << "ID" << p.col << "\tre: " << p.regular_Expression;
            if (p.name == "1")
            {
                cout << "\twho have real content re: " << name_re_expression[p.regular_Expression];
            }
            cout << endl;
        }
    }

    void addRe(Base &newBase) // 更新新的re的函数
    {
        // MARK NFA1的空间扩容
        int diff1 = (NFA.size() - rowNum);
        if (abs(diff1) <= 10)
        {
            for (int i = 0; i < NFA_1_SIZE_ADD; ++i)
            {
                // 多加入一行，共加入NFA_1_SIZE_ADD行，每一行的所对应的列长度为NFA_SIZE_RE_2
                NFA.push_back(vector<vector<int>>(NFA_SIZE_RE_2));
            }
        }

        /**
         * 会自动控制size和rowNum
         * 然后会赋值row和col给newbase
         */
        size1++;
        rowNum++;
        expressionToColumn[newBase.regular_Expression] = size1;
        newBase.row = rowNum;
        newBase.col = expressionToColumn[newBase.regular_Expression];
        NFA[rowNum][size1].push_back(rowNum + 1);
        rowNum++;
        resualt.push_back(newBase);
    }

    void updateParalle() // 转化为映射后的表达式
    {
        for (int i = 0; i < origin.size(); i++)
        {
            if (inPunc(origin.substr(i, 1)))
            {
                updatedString += (origin.substr(i, 1));
                continue;
            }
            Base searchOne = readBase(origin, i);                                  // 找
            searchOne = resualt[expressionToColumn[searchOne.regular_Expression]]; // 映射
            updatedString += to_string(searchOne.col);
            updatedString += " "; // 添加

            if (searchOne.regular_Expression.size() != 0) // 转移
            {
                i = i + searchOne.regular_Expression.size() - 1;
            }
        }

        cout << "更新添加与符号前的表达式：" << updatedString << endl;

        string s = updatedString;
        updatedString = ""; // 补充与运算

        for (int i = 0; i < s.size(); i++)
        {
            if (isdigit(s[i]) || s[i] == '(')
            {
                for (int j = i - 1; j >= 0; j--)
                {
                    if (s[j] == ' ')
                    {
                        continue;
                        // break;
                    }
                    else if ((s[j] != '|' && s[j] != '(') || (isdigit(s[j])))
                    {
                        updatedString += "&";
                        break;
                    }
                    else
                    {
                        break;
                    }
                }
            }

            // 对应的列的正则项目的序号可能是两位数
            int k = i + 1;
            if (isdigit(s[i]))
            {
                for (k; k < s.size(); k++)
                {
                    if (isdigit(s[k]) == false)
                    {
                        break;
                    }
                }
            }
            // updatedString.push_back(s[i]);
            updatedString += s.substr(i, k - i);
            i = k - 1;
        }
        cout << "加入了与符号的表达式：" << updatedString << endl;
    }

    void showNFA()
    {

        if (SHOW_NFA == 0)
        {
            return;
        }
        // 保存默认的输出格式
        ios_base::fmtflags defaultFlags = cout.flags();
        streamsize defaultWidth = cout.width();
        cout << "NFA1的内容" << endl;

        cout << left;
        cout << setw(M_OUTPUT_LEN) << "re:";
        for (int i = 0; i <= baseLength; i++)
        {
            cout << setw(M_OUTPUT_LEN) << to_string(i) + ":" + resualt[i].regular_Expression;
        }
        cout << endl;

        for (int i = 1; i <= rowNum; i++)
        {
            cout << setw(M_OUTPUT_LEN) << "row:" + to_string(i) + ":";
            for (int j = 0; j <= baseLength; j++)
            {
                cout << setw(M_OUTPUT_LEN) << vectorToString(NFA[i][j]);
            }
            cout << endl;
        }

        // 恢复默认的输出格式
        cout.flags(defaultFlags);
        cout.width(defaultWidth);
    }

    void showNFA2()
    {

        if (SHOW_NFA == 0)
        {
            return;
        }
        // 保存默认的输出格式
        ios_base::fmtflags defaultFlags = cout.flags();
        streamsize defaultWidth = cout.width();
        cout << "NFA2的内容" << endl;

        cout << left;
        cout << setw(M_OUTPUT_LEN) << "re:";
        for (int i = 0; i <= baseLength; i++)
        {
            cout << setw(M_OUTPUT_LEN) << to_string(i) + ":" + resualt[i].regular_Expression;
        }
        cout << endl;

        for (int i = 1; i < NFA2_node_number; i++)
        {
            cout << setw(M_OUTPUT_LEN) << "row:" + to_string(i) + ":";
            for (int j = 0; j <= baseLength; j++)
            {
                cout << setw(M_OUTPUT_LEN) << vectorToString(NFA2[i][j]);
            }
            cout << endl;
        }

        // 恢复默认的输出格式
        cout.flags(defaultFlags);
        cout.width(defaultWidth);
        //
    }

    vector<string> mid_to_end(string updatedString)
    {
        map<string, int> isp;
        map<string, int> icp;
        // vector<string> punc_s({"|", "*", "+", "?", "(", ")"}); // 运算符号
        isp["("] = 1;
        isp[")"] = 6;
        isp["|"] = 3;
        isp["&"] = 5;
        // isp["*"] = 5;
        // isp["?"] = 5; // 闭包和？
        // isp["+"] = 5;

        // icp
        icp["("] = 6;
        icp[")"] = 1;
        icp["|"] = 2;
        icp["&"] = 4;

        vector<string> specialPunc({"*", "+", "?"});
        unordered_set<string> specialPuncSet(specialPunc.begin(), specialPunc.end());

        string s = updatedString;
        stack<string> s1;
        stack<string> s2;

        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == ' ')
            {
                continue;
            }
            if (isdigit(s[i]))
            {
                int pos = i;
                int res = 0;
                while (isdigit(s[pos]))
                {
                    pos++;
                }
                s1.push((s.substr(i, pos - i)));
                i = pos - 1;
                continue;
            }
            // 优先处理后缀运算符
            else if (specialPuncSet.find(s.substr(i, 1)) != specialPuncSet.end())
            {
                s1.push(s.substr(i, 1));
            }
            else
            {
                if (s2.empty() || isp[s2.top()] < icp[s.substr(i, 1)]) // 如果外界的优先级更加的大的话
                {
                    cout << "s2栈内压入了字符：" << s[i] << endl;
                    s2.push(s.substr(i, 1));
                }
                else if (isp[s2.top()] > icp[s.substr(i, 1)])
                {
                    // 内部的运算符号更大的话，寻找比外界小的情况，知道符号为空为止
                    while (!s2.empty() && isp[s2.top()] > icp[s.substr(i, 1)])
                    {
                        // 弹出输出位置
                        string dot1 = s2.top();
                        s1.push(dot1);
                        s2.pop();
                    } // 离开循环的时候，栈内的顶层要么就是空了，要么就是顶层小于等于本身了

                    i -= 1; // 为什么要 -1 呢，因为这个是for循环对比while循环而言的弊端
                            // 让本次操作不进行压栈操作，压入栈中的操作交给等于和小于来完成
                }
                else // 等于的情况
                {
                    if (s2.top() == "(")
                    {
                        s2.pop();
                    }
                }
            }
        }

        while (!s2.empty())
        {
            cout << "剩余存在" << endl;
            s1.push(s2.top());
            s2.pop();
        }
        vector<string> res;
        while (!s1.empty())
        {
            res.push_back(s1.top());
            s1.pop();
        }
        reverse(res.begin(), res.end());

        string res2 = "";
        for (auto p : res)
        {
            res2 += (p + " ");
        }
        cout << "后缀转换后的结果为" << res2 << endl;
        ;
        return res;
    }

    MyObject NFA2_addEdge()
    {
        int start = NFA2_node_number;
        NFA2_node_number += 2;
        // MARK 已经扩充NFA2的尺寸，一次扩大NFA_2_SIZE_ADD行
        int diff1 = (NFA2.size() - NFA2_node_number);
        if (abs(diff1) <= 10)
        {
            for (int i = 0; i < NFA_2_SIZE_ADD; ++i)
            {
                // 多加入一行，共加入NFA_2_SIZE_ADD行，每一行的所对应的列长度为NFA_SIZE_RE_2
                NFA2.push_back(vector<vector<int>>(NFA_SIZE_RE_2));
            }
        }
        return MyObject(start, start + 1);
    }

    void cal(vector<string> back)
    {
        vector<string> &s = back;
        stack<MyObject> numbers;
        for (int i = 0; i < s.size(); i++)
        {
            // 数字
            if (isdigit(s[i][0]))
            {
                int t = stoi(s[i]); // t是基本正则的标号
                NFA2[NFA2_node_number][t].push_back(NFA2_node_number + 1);
                MyObject newObj(NFA2_node_number, NFA2_node_number + 1);
                newObj.value = to_string(t);
                numbers.push(newObj);
                NFA2_node_number += 2;
                // （如果没有设置起点和终点）设置起点和终点
                if (nfa2_start == -1 && nfa2_end == -1) // 实际上，只需要初始化这一次
                {
                    nfa2_start = newObj.start;
                    nfa2_end = newObj.end;
                }

                continue;
            }

            Base newBase;
            try
            {
                if (s[i] == "&")
                {
                    MyObject num2 = numbers.top(); // 先得到右运算数
                    numbers.pop();
                    MyObject num1 = numbers.top();
                    numbers.pop();
                    cout << num2.value << " " << num1.value << "与运算一次" << endl;
                    NFA2[num1.end][0].push_back(num2.start);
                    MyObject newNum(num1.start, num2.end); // 不需要添加新的边
                    numbers.push(newNum);

                    // 起点和终点
                    nfa2_start = newNum.start;
                    nfa2_end = newNum.end;
                }
                else if (s[i] == "*")
                {
                    MyObject num1 = numbers.top();
                    numbers.pop();
                    MyObject num2 = NFA2_addEdge();
                    NFA2[num2.start][0].push_back(num2.end);   // 全空
                    NFA2[num2.start][0].push_back(num1.start); // 新开头指向被运算的开头
                    NFA2[num1.end][0].push_back(num2.end);     // 旧的结尾到新的结尾
                    // 到达尾巴一定是唯一的
                    NFA2[num1.end][0].push_back(num1.start); // 自环：尾巴-》开头为空
                    numbers.push(num2);

                    // 起点和终点
                    nfa2_start = num2.start;
                    nfa2_end = num2.end;
                }
                else if (s[i] == "+")
                {
                    MyObject num1 = numbers.top();
                    numbers.pop();
                    MyObject num2 = NFA2_addEdge();
                    // NFA2[num2.start][0].push_back(num2.end);   // 全空
                    NFA2[num2.start][0].push_back(num1.start); // 新开头指向被运算的开头
                    NFA2[num1.end][0].push_back(num2.end);     // 旧的结尾到新的结尾
                    // 到达尾巴一定是唯一的
                    NFA2[num1.end][0].push_back(num1.start); // 自环：尾巴-》开头为空
                    numbers.push(num2);

                    // 起点和终点
                    nfa2_start = num2.start;
                    nfa2_end = num2.end;
                }
                else if (s[i] == "?")
                {
                    MyObject num1 = numbers.top();
                    numbers.pop();
                    // 到达尾巴一定是唯一的
                    NFA2[num1.start][0].push_back(num1.end); // 问号-开头-》结尾为空
                    numbers.push(num1);

                    // 起点和终点
                    nfa2_start = num1.start;
                    nfa2_end = num1.end;
                }
                else if (s[i] == "|")
                {
                    MyObject num2 = numbers.top();
                    numbers.pop();
                    MyObject num1 = numbers.top();
                    numbers.pop();
                    cout << num2.value << " " << num1.value << "或运算一次" << endl;
                    MyObject newNum = NFA2_addEdge();
                    NFA2[newNum.start][0].push_back(num1.start); // 一个节点连接两个边的开头
                    NFA2[newNum.start][0].push_back(num2.start);
                    NFA2[num1.end][0].push_back(newNum.end); // 两个边的结尾连接到同一个节点
                    NFA2[num2.end][0].push_back(newNum.end);
                    numbers.push(newNum);

                    // 起点和终点
                    nfa2_start = newNum.start;
                    nfa2_end = newNum.end;
                }
            }
            catch (...)
            {
                cout << "NFA.CAL函数，发生运算错误" << endl;
            }
        }
    }
    void make_calculate()
    {
        updateParalle();
        cal(mid_to_end(updatedString));
        cout << "运算结束，获取的 start:" << nfa2_start << "\tend:" << nfa2_end << endl;
    }

    string vectorToString(vector<int> t)
    {
        string res = "{";
        for (auto p : t)
        {
            res += to_string(p) + ",";
        }
        res += "}";
        return res;
    }
};

#endif // RE_TO_DFA